1
Các nguyên lý của tối thiểu hóa không ràng buộc
MATH008Lesson 9
00:00
Chúng ta chuyển từ sự tồn tại lý thuyết của cực tiểu sang động cơ thuật toán trong tối ưu hóa. Mục tiêu cốt lõi của chúng ta là tối thiểu hóa $f(x)$ (9.1) trong đó $f: \mathbf{R}^n \to \mathbf{R}$ là hàm lồi và khả vi hai lần liên tục. Vì $f$ khả vi và lồi, điều kiện cần và đủ để một điểm $x^*$ là tối ưu là $\nabla f(x^*) = 0$.

Khung thuật toán

Các nghiệm số xây dựng một dãy giảm dần: Một dãy các điểm $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ sao cho $f(x^{(k)}) \to p^*$ khi $k \to \infty$. Mỗi bước cập nhật vị trí thông qua $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, trong đó $\Delta x$ là một hướng giảm.

Khởi tạo và hội tụ

Các phương pháp được mô tả trong chương này yêu cầu một điểm khởi đầu phù hợp $x^{(0)}$. Điểm khởi đầu phải nằm trong $\text{dom } f$, đồng thời tập mức thấp $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ phải là tập đóng. Điều này đảm bảo dãy vẫn nằm trong vùng ổn định nơi ma trận Hessian cung cấp thông tin hữu ích.

Hướng giảm

Hướng đơn giản nhất là $\Delta x = -\nabla f(x)$. Tuy nhiên, hiệu quả thường đòi hỏi phải tính đến các hình học khác nhau thông qua hướng giảm dốc nhất:

  • Chuẩn bậc hai: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
  • Chuẩn $L_\infty$: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Giảm theo tọa độ).

Mô hình bậc hai và miền tin cậy

Phương pháp Newton sử dụng xấp xỉ Taylor bậc hai: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Biểu thức bậc hai này đạt cực tiểu khi $v = \Delta x_{nt}$ (bước Newton). Chúng ta định nghĩa một miền tin cậy: tập hợp $\{v \mid \|v\|_2 \le \gamma\}$. Tham số $\gamma$ phản ánh mức độ tin tưởng của chúng ta vào mô hình bậc hai. Khi mô hình chính xác, chúng ta giải tìm hướng thông qua $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ trong các hệ thống KKT.

🎯 Các nguyên lý cốt lõi về hội tụ
Hiệu quả được đo bằng tốc độ mà sai số $f(x^{(k)}) - p^*$ biến mất. Đối với các hàm lồi mạnh, sai số $f(x^{(k)}) - p^*$ hội tụ về 0 ít nhất nhanh như một chuỗi hình học. Trong bối cảnh các phương pháp số lặp, điều này được gọi là hội tụ tuyến tính.
  • Giới hạn bất tối ưu: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, đúng nếu $\lambda(x) < 1$.
  • Tổng tự đồng dạng: Nếu $f_1, f_2$ là tự đồng dạng, thì $f_1 + f_2$ cũng là tự đồng dạng.
  • Độ thưa của ma trận Hessian: Hiệu quả được tăng lên nếu điều kiện cấu trúc băng của ma trận Hessian: $\nabla^2 f(x)_{ij} = 0$ khi $|i-j| > k$ được thỏa mãn.